/* -*-  Mode:C; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * An implementation of the Congestion Manager (CM) for Linux.
 * This file implements the binomial congestion control
 * in CM.
 */
#include <linux/config.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <net/cm.h>
#include <net/cm_bincongctl.h>
#include <linux/wanpipe.h>
#include <net/cm_debug.h>

#ifdef CONFIG_CM_BINOMIAL
/*
 * Initialize congestion controller state when a new CM is instantiated 
 * for this destination (macroflow) using binomial congestion control
 * .  Called by cm_open().
 */
void cmbincc_init(cm_congctl_t *cmbincc)
{
        CM_DPRINTF(CM_DEBUG_FUNCALL|CM_DEBUG_MACROFLOW_INIT,
		   "cm_debug:  %s:  initting CC %p for a new macroflow\n",
		   __FUNCTION__, cmbincc);

	cmbincc->state.size = cmbincc->mflow->mtu;
	cmbincc->state.outstanding = 0;	/* nothing sent so far */
	cmbincc->state.last_size = 0;
	cmbincc->state.last_time = 0;	/* will be set on first xmit */
	cmbincc->state.last_loss = 0;
	cmbincc->state.srtt = 0;	/* former value: CM_SRTT_DEFAULT */
	cmbincc->state.rttmin = 0;
	cmbincc->state.rttdev = 0;     
	cmbincc->state.rto = CM_MAX_RTO;
	cmbincc->state.cwnd = cmbincc->mflow->mtu;
	cmbincc->state.ssthresh = 32768;/* XXX random arbitrary default */
	cmbincc->congctl_param = 0.5;   /*binomial congctl parameter 0=>AIMD*/
	cmbincc->congctl_type = 1;

	cmbincc->ops.update = cmbincc_update;
	cmbincc->ops.query = cmbincc_query;
	cmbincc->ops.notify = cmbincc_notify;
	cmbincc->ops.wakeup = cmbincc_wakeup;
}

/*
 * Called in first cm_update() call.
 */
inline void cmbincc_startup(cm_congctl_t *cmbincc, int nrecd, double rtt, 
			 int lossmode)
{
	/* printk("entering cmbincc_startup\n"); */
	if (rtt > 0) {
		cmbincc->state.rttmin = cmbincc->state.srtt = rtt;
	}
}

/* 
 * Go back into slow start.
 */
inline void cmbincc_restart(cm_congctl_t *cmbincc, u32 now)
{
	cmbincc->state.ssthresh = cmbincc->state.cwnd;
	cmbincc->state.cwnd = cmbincc->state.size; /* 1 packet */
	cmbincc->state.last_loss = now;
	CM_DPRINTF(CM_DEBUG_CONGCTL, "BIN_RESTART %d cwnd %d ssthresh %d \n",
		   now, cmbincc->state.cwnd,cmbincc->state.ssthresh);
}

inline void cmbincc_decrease(cm_congctl_t *cmbincc, u32 now)
{
	/* Multiplicative decrease at most once every round-trip */
	/*not sure of check below. im many simulations, I have 
	 *commented this out 
	 */
	if ((now - cmbincc->state.last_loss)*10000  /* jiffies -> us */
	    >= cmbincc->state.srtt) {    /* XXX use rttmin? */
		/* check for binomial ctrl parameter here */
		if (cmbincc->congctl_param < 0.1)
			cmbincc->state.cwnd = 
				(cmbincc->state.cwnd >> CM_DECR_SHIFT);
		else {
			CM_DPRINTF(CM_DEBUG_CONGCTL, "window %d\n",
				   cmbincc->state.cwnd);
			cmbincc->state.cwnd -= 
				23.0*pow(cmbincc->state.cwnd, 0.5); 
			CM_DPRINTF(CM_DEBUG_CONGCTL, "window %d\n",
				   cmbincc->state.cwnd);
		}
		if (cmbincc->state.cwnd < cmbincc->state.size)
			cmbincc->state.cwnd = cmbincc->state.size;
		cmbincc->state.ssthresh = cmbincc->state.cwnd;
		cmbincc->state.last_loss = now;
		CM_DPRINTF(CM_DEBUG_CONGCTL,
			   "BIN_DECREASE %d cwnd %d ssthresh %d \n",
			   now, cmbincc->state.cwnd, cmbincc->state.ssthresh);
	} else {
		CM_DPRINTF(CM_DEBUG_CONGCTL,
			   "no cut down in decrease %d %d %d\n",
			   now, cmbincc->state.last_loss, cmbincc->state.srtt);
	}
}

/*
 * Increase algorithm does byte counting to account for infrequent feedback.
 * Bursts are avoided by ensuring that sender paces (shapes) packets out.
 */
inline void cmbincc_increase(cm_congctl_t *cmbincc, int nrecd)
{
	__u32 now = (__u32)(jiffies);
	if (cmbincc->state.cwnd >= cmbincc->state.ssthresh) {
		if  (cmbincc->congctl_param < 0.1) {
			printk("cong ctl parameter %d\n",cmbincc->congctl_param); 
			cmbincc->state.cwnd += 
				min ((int)((nrecd*cmbincc->state.size)/
					   cmbincc->state.cwnd), cmbincc->state.size); 
		} else {
			/* hardcoded as SQRT algorithm */
			CM_DPRINTF(CM_DEBUG_CONGCTL,
				   "SQRT before inc: cwnd %d\n",
				   cmbincc->state.cwnd);
			cmbincc->state.cwnd += 
				min ((int)((nrecd*58500)/
					   ((cmbincc->state.cwnd)*pow(cmbincc->state.cwnd,0.5))), cmbincc->state.size);
			CM_DPRINTF(CM_DEBUG_CONGCTL,
				"SQRT inc: cwnd %d pow %d\n",
				cmbincc->state.cwnd,
				pow(cmbincc->state.cwnd,0.5));
		}
	} else {/* don't jump over ssthresh */
		cmbincc->state.cwnd = min(cmbincc->state.cwnd + nrecd, 
					  cmbincc->state.ssthresh);
	}
	CM_DPRINTF(CM_DEBUG_CONGCTL,
		   "BIN_INCREASE %d cwnd %d ssthresh %d \n",
		   now, cmbincc->state.cwnd, cmbincc->state.ssthresh);
}

/* RTO estimation 
 * combined RTO estimation and bounding rto from tcp code
 * do not need two separate 2 line functions
 */

inline void cmbincc_update_rto(cm_congctl_t *cmbincc) 
{
        cmbincc->state.rto = (cmbincc->state.srtt >> CM_RTTSHIFT) + cmbincc->state.rttdev;
	/* tcp uses snd_cwnd instead of cwnd below; check if this is fine */
        cmbincc->state.rto += (cmbincc->state.rto >> CM_RTTDEVSHIFT) + (cmbincc->state.rto >> (cmbincc->state.cwnd-1));
        if (cmbincc->state.rto > 120*HZ)
                cmbincc->state.rto = 120*HZ;
        if (cmbincc->state.rto < HZ/5)
                cmbincc->state.rto = HZ/5;
}


/* 
 * Estimate round-trip time.
 */
inline void cmbincc_update_rtt(cm_congctl_t *cmbincc, u32 rtt)
{
	u32 shrinkage = 0;
	u32 mshrinkage = 0;
	int rtterror = 0;	

	if (rtt == 0)
		return;
	/* dividing by 8 and multiplying by 7 tends to result in 0 too often */
	/* this is equivalent and subtraction isn't too expensive */
	shrinkage = cmbincc->state.srtt >> CM_RTTSHIFT;
	rtterror = rtt - cmbincc->state.srtt;
	cmbincc->state.srtt = cmbincc->state.srtt - shrinkage;
	cmbincc->state.srtt += rtt >> CM_RTTSHIFT;
	if (rtt < cmbincc->state.rttmin)
		cmbincc->state.rttmin = rtt;
	/* hacked in rttdev calculation too, not checked yet*/
	if (rtterror < 0) rtterror = -rtterror;
	mshrinkage = cmbincc->state.rttdev >> CM_RTTDEVSHIFT;
	cmbincc->state.rttdev -= mshrinkage;
	cmbincc->state.rttdev += rtterror >> CM_RTTDEVSHIFT;
	cmbincc_update_rto(cmbincc);
}

void cmbincc_update(cm_congctl_t *cmbincc, int nsent, int nrecd, 
		 u32 rtt, int lossmode)
{
	__u32 now = (__u32)(jiffies);
	int changed = 0;
	int outs = cmbincc->state.outstanding;
	int sent;

	if (nsent == 0) 
		return;
	CM_DPRINTF(CM_DEBUG_CONGCTL,
		   "update: outstanding changes from %d to %d \n",
		   cmbincc->state.outstanding,
		   cmbincc->state.outstanding-nsent);
	cmbincc->state.outstanding -= nsent; /* um... what about reordering? */

	if (cmbincc->state.srtt == 0 && rtt != 0) /*&& lossmode == CM_NOLOSS)*/
		/* XXX */
		cmbincc_startup(cmbincc, nrecd, rtt, lossmode);/* slow start */

	/* Assuming no reordering fixes.  Need to modify for reordering. */
	switch (lossmode) {
	case (CM_ECN):
	case (CM_TRANSIENT):
		cmbincc_decrease(cmbincc, now);
		changed = 1;
		cmbincc->state.last_backoff = 0;
		cmbincc->state.backoff = 1;
		break;
	case (CM_PERSISTENT):
		cmbincc_restart(cmbincc, now);
		changed = 1;
		cmbincc->state.last_backoff = 0;
		cmbincc->state.backoff = 1;
		break;
/*
	case (CM_PARTIALACK):
		Don't do anything for partial acks.
		break;
*/
	default:  /* no losses */
		cmbincc_update_rtt(cmbincc, rtt);
		/* Commented Deepak: dont know why? */
		/* In last test, commented because wasn't allowing
                 * inc. in many cases */
		/* if ((cmbincc->state.outstanding + nsent) > 
		 *   ((cmbincc->state.cwnd /2)))
		 */
		cmbincc_increase(cmbincc, nrecd);
		changed = 1;
		cmbincc->state.last_backoff = 0;
		cmbincc->state.backoff = 1;
		break;
	}
	cmbincc_update_rate(cmbincc);
}

void cmbincc_query(cm_congctl_t *cmbincc, double *bw, double *srtt,
		   double *rttvar)
{


	*bw = (double) cmbincc->state.rate;
	*srtt = cmbincc->state.srtt;
}

void cmbincc_notify(cm_congctl_t *cmbincc, int nsent)
{
	__u32 now = (__u32)(jiffies);

	CM_DPRINTF(CM_DEBUG_CONGCTL,
		   "notify: outstanding changes from %d to %d \n",
		   cmbincc->state.outstanding,
		   cmbincc->state.outstanding+nsent);
	cmbincc->state.outstanding += nsent;
	if ( (cmbincc->state.rttmin == 0) ||
	     (((now - cmbincc->state.last_time) * 10000 /* jiffies -> us */
	      * cmbincc->state.cwnd / cmbincc->state.rttmin)
	     > cmbincc->state.last_size)) {
		/* pace is slower than required */
		cmbincc->state.last_time = now;
		cmbincc->state.last_size = nsent;
	} else {
		/* sent too soon... need to compensate on next send */
		cmbincc->state.last_size += nsent;/* so inflate last_size */
	}
}

void cmbincc_wakeup(cm_congctl_t *cmbincc) {
	cm_sched_t *sched = cmbincc->mflow->sched;
	__u32 now = (__u32)(jiffies);
	int pacing_est = cmbincc->state.size;
	int maxburst = CM_BINCC_MAXBURST;
	int outstanding = cmbincc->state.outstanding;

#if 0
	if (cmbincc->state.rttmin != 0) {
		pacing_est = (cmbincc->state.cwnd * 
			      (now - cmbincc->state.last_time + 1)) / 
			cmbincc->state.rttmin;
		if (pacing_est < cmbincc->state.last_size)
			/* too soon for pacing */
			return;
		pacing_est -= cmbincc->state.last_size;
	} 
#endif
	while (/* (pacing_est >= cmbincc->state.size) && */
	       ((cmbincc->state.cwnd >= outstanding + cmbincc->state.size)) &&
	       (maxburst-- > 0)) {
		/* give up the lock here since callbacks from the
		   scheduler may need to get the lock */
		spin_unlock_bh(&(cmbincc->ccstate_lock));
		/* send a pkt */
		cms_schedule(sched);
		spin_lock_bh(&(cmbincc->ccstate_lock));
		pacing_est -= cmbincc->state.size;
		outstanding += cmbincc->state.size;
	}

}

#endif



/* compute rate on mflow --- either cwnd or srtt has changed */
/* then check each flow on the mflow:			     */
/* if rate callback bounded by thresholds, check them and do callback */
/*	if warranted                                         */
/* if rate callback enabled without thresholds, do it        */
void cmbincc_update_rate(cm_congctl_t *cmbincc)
{
        cm_macroflow_t *mflow = cmbincc->mflow;
	int nonzero_srtt = cmbincc->state.srtt;
	cm_flow_t *flow;
	double newrate, newfrate;
	int irate;
	if (cmbincc->state.srtt == 0) nonzero_srtt = CM_RTT_DEFAULT;
#ifdef CM_AGING
	cmbincc->state.rate = (double) cmbincc->state.cwnd/(nonzero_srtt * 
					    cmbincc->state.backoff);
#else
	cmbincc->state.rate = (double) cmbincc->state.cwnd/nonzero_srtt;
#endif
	irate = cmbincc->state.rate;
	CM_DPRINTF(CM_DEBUG_CONGCTL,
		   "mflow rate = %d cwnd %d srtt %d\n",
		   irate, cmbincc->state.cwnd, nonzero_srtt);
	newrate = cmbincc->state.rate;
	flow = mflow->flows;
	while (flow) {
		if (!(flow->downthreshmult < 0.0)) { /* if enabled */
		   newfrate = newrate * cms_query_share(mflow->sched,flow);
		   if (newfrate < flow->downthreshmult*flow->lastrate ||
	    	    	newfrate > flow->upthreshmult*flow->lastrate) {
			flow->lastrate = newfrate;
			flow->ratechange = 1;
			if (flow->do_callback) cmapp_send_wakeup(flow);
		   }
		}
		flow = flow->next;
	}
}





